package leetcode.f1t100;

import java.util.*;

/**
 * 给一串数字, 得到手机9个按键可能得到的内容值
 * https://leetcode.com/problems/letter-combinations-of-a-phone-number/
 *
 * @Author lichongxiao
 * @Date 2022/9/28 16:36
 */
public class Q17_LatterCombinationsOfAPhoneNumber {

    public static void main(String[] args) {
        List<String> list = new Q17_LatterCombinationsOfAPhoneNumber().letterCombinations("23");
        for (String s : list) {
            System.out.println(s);
        }
    }

    /**
     * 大佬做法
     *
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        LinkedList<String> ansList = new LinkedList<>();
        if (digits == null || digits.isEmpty()) {
            return ansList;
        }
        String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        while (ansList.peek().length() < digits.length()) {
            String remove = ansList.remove();
            String mapStr = mapping[digits.charAt(remove.length()) - '0'];
            for (char c : mapStr.toCharArray()) {
                ansList.addLast(remove + c);
            }
        }
        return ansList;
    }

    /**
     * 我的实现
     *
     * @param digits
     * @return
     */
    public List<String> letterCombinations2(String digits) {
        if (digits == null || "".equals(digits)) {
            return new ArrayList<String>();
        }
        Node root = new Node();
        List<Node> leafNodeList = new ArrayList<>();
        List<Node> nextLeafNodeList = new ArrayList<>();
        List<Node> ansNodeList = new ArrayList<>();
        leafNodeList.add(root);
        char[] chars = digits.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            switch (chars[i]) {
                case '2':
                    for (Node node : leafNodeList) {
                        node.setNodes(new Node[]{new Node('a'), new Node('b'), new Node('c')});
                        nextLeafNodeList.add(node.getNodes()[0]);
                        nextLeafNodeList.add(node.getNodes()[1]);
                        nextLeafNodeList.add(node.getNodes()[2]);
                    }
                    break;
                case '3':
                    for (Node node : leafNodeList) {
                        node.setNodes(new Node[]{new Node('d'), new Node('e'), new Node('f')});
                        nextLeafNodeList.add(node.getNodes()[0]);
                        nextLeafNodeList.add(node.getNodes()[1]);
                        nextLeafNodeList.add(node.getNodes()[2]);
                    }
                    break;
                case '4':
                    for (Node node : leafNodeList) {
                        node.setNodes(new Node[]{new Node('g'), new Node('h'), new Node('i')});
                        nextLeafNodeList.add(node.getNodes()[0]);
                        nextLeafNodeList.add(node.getNodes()[1]);
                        nextLeafNodeList.add(node.getNodes()[2]);
                    }
                    break;
                case '5':
                    for (Node node : leafNodeList) {
                        node.setNodes(new Node[]{new Node('j'), new Node('k'), new Node('l')});
                        nextLeafNodeList.add(node.getNodes()[0]);
                        nextLeafNodeList.add(node.getNodes()[1]);
                        nextLeafNodeList.add(node.getNodes()[2]);
                    }
                    break;
                case '6':
                    for (Node node : leafNodeList) {
                        node.setNodes(new Node[]{new Node('m'), new Node('n'), new Node('o')});
                        nextLeafNodeList.add(node.getNodes()[0]);
                        nextLeafNodeList.add(node.getNodes()[1]);
                        nextLeafNodeList.add(node.getNodes()[2]);
                    }
                    break;
                case '7':
                    for (Node node : leafNodeList) {
                        node.setNodes(new Node[]{new Node('p'), new Node('q'), new Node('r'), new Node('s')});
                        nextLeafNodeList.add(node.getNodes()[0]);
                        nextLeafNodeList.add(node.getNodes()[1]);
                        nextLeafNodeList.add(node.getNodes()[2]);
                        nextLeafNodeList.add(node.getNodes()[3]);
                    }
                    break;
                case '8':
                    for (Node node : leafNodeList) {
                        node.setNodes(new Node[]{new Node('t'), new Node('u'), new Node('v')});
                        nextLeafNodeList.add(node.getNodes()[0]);
                        nextLeafNodeList.add(node.getNodes()[1]);
                        nextLeafNodeList.add(node.getNodes()[2]);
                    }
                    break;
                case '9':
                    for (Node node : leafNodeList) {
                        node.setNodes(new Node[]{new Node('w'), new Node('x'), new Node('y'), new Node('z')});
                        nextLeafNodeList.add(node.getNodes()[0]);
                        nextLeafNodeList.add(node.getNodes()[1]);
                        nextLeafNodeList.add(node.getNodes()[2]);
                        nextLeafNodeList.add(node.getNodes()[3]);
                    }
                    break;
            }
            leafNodeList = nextLeafNodeList;
            nextLeafNodeList = new ArrayList<>();
        }
        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();
        for (Node node : root.getNodes()) {
            stack.add(node);
        }
        List<String> result = new ArrayList<>();
        StringBuilder s = new StringBuilder();
        while (!stack.empty()) {
            Node node = stack.peek();
            if (set.contains(node)) {
                stack.pop();
                s.deleteCharAt(s.length() - 1);
                continue;
            } else {
                set.add(node);
                s.append(node.getC());
            }
            if (node.getNodes() != null && node.getNodes().length > 0) {
                for (int i = 0; i < node.getNodes().length; i++) {
                    stack.push(node.getNodes()[i]);
                }
            } else {
                result.add(s.toString());
            }
        }
        return result;
    }

    public class Node {
        private char c;
        private Node[] nodes;

        public Node() {

        }

        public Node(char c) {
            this.c = c;
        }

        public char getC() {
            return c;
        }

        public void setC(char c) {
            this.c = c;
        }

        public Node[] getNodes() {
            return nodes;
        }

        public void setNodes(Node[] nodes) {
            this.nodes = nodes;
        }
    }
}
